package trimMean;

import java.util.Arrays;

public class Solution {
    public double trimMean(int[] arr) {
        // 暴力
        Arrays.sort(arr);
        int sum = 0;
        int i = (int)(arr.length*0.05);
        int end = (arr.length-i);
        i--;
        while (i<end){
            sum+=arr[i];
            i++;
        }
        return sum;

        // 快速选择算法
        // 求前k大的数
        // 分成两个区间 左区间的值<m 右区间的值>m
        // 如果左区间的元素个数==k 返回左区间

    }

    // 快速选择算法
//    private static int quickSelect(int l,int r,int []arr,int k){
//        if(l==r){
//            return arr[l];// 当前区间只有一个元素
//        }
//        // 否则进行排序和查找
//        int i = l-1;
//        int j = r+1;
//        int pivot = arr[l];//本次比较的对象
//        while(i<j){
//            while (arr[++i]<arr[l]);
//            while (arr[--j]<arr[l]);
//            if(i<j){
//                int t = arr[i];
//                arr[i] = arr[j];
//                arr[j] = t;
//            }
//        }
//        int s1 = j - l + 1;
//        if(s1 >= k){
//            return quickSelect(l,i - 1,arr,k);
//        }else{
//            //否则排序右边数组
//            k = k - s1;
//            return quickSelect( i,r,arr,k);
//        }
//    }

}
